package watercalc;

import java.util.Collections;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.LinkedHashSet;

import watercalc.comparators.StabilityComparator;
import watercalc.comparators.HeightAndCapacityComparator;

public class Solver {

	@SuppressWarnings("unchecked")
	public static void solve(Graph iGraph) {

		Iterator<Vertex> iterator;
		ArrayList<Vertex> vertexes = (ArrayList<Vertex>) iGraph.mVertexes.clone();
		
		// After parsing the only node for which we have stable status is the sink. We
		// iterate from it, climbing up the borders of the container and moving through
		// the higher vertexes we find. For each of these vertexes we can state they have
		// 0 capacity and stable status as their content directly goes into the sink.
		// This way we easily restrict search space for the second part of the algorithm.
		while (!vertexes.isEmpty()) {
			Collections.sort(vertexes, new StabilityComparator());
			Vertex current = vertexes.get(0);
			if (!current.stable) {
				break;
			}
			vertexes.remove(current);
			iterator = current.neighbours.iterator();
			while(iterator.hasNext()) {
				Vertex next = iterator.next();
				if ( current.height <= next.height ) {
					next.capacity = 0;
					next.stable = true;
				}
			}
		}

		System.out.println("After preprocessing:");
		iGraph.display(Graph.CAPACITIES);

		// Processing phase:
		// 1 Sort the unstable vertexes by height plus capacity
		// 2 Select the lowest as current
		// 3 Find the cluster of neighbours with the same height and capacity as current
		//   if they exists (I refer to these vertexes as "plateau").
		// 4 Find the wall of the plateau (the border vertexes)
		// 5 Shortest vertex of the wall determines if selected plateau's capacity has to
		//   be incremented.
		// 6 If shortest wall is stable, mark all plateau as stable (there is no way
		//   its capacity can further increase).
		while (!vertexes.isEmpty()) {
			Collections.sort(vertexes, new HeightAndCapacityComparator());
			Vertex current = vertexes.get(0);
			if (current.stable) {
				vertexes.remove(current);
			} else {
				updatePlateauCapacity(current);
			}
		}

		System.out.println("Container capacities:");
		iGraph.display(Graph.CAPACITIES);

	}

	// Find the plateau of input vertex (the lowest height + capacity is chosen at each step),
	// update its capacity and marks stable if needed.
	// I call "plateau" a cluster of vertexes who have same height and capacity.
	static void updatePlateauCapacity(Vertex iVertex) {
		LinkedHashSet<Vertex> plateau = getPlateau(iVertex);
		LinkedHashSet<Vertex> wall = getWall(plateau);
		Vertex shortestWall = getShortestWall(wall);
		updateCapacities(plateau, shortestWall);
	}

	// Find the cluster of neighbours with the same height and capacity as iVertex
	static LinkedHashSet<Vertex> getPlateau(Vertex iVertex) {
		Iterator<Vertex> iterator, iterator2;
		LinkedHashSet<Vertex> plateau = new LinkedHashSet<Vertex>();
		LinkedHashSet<Vertex> alreadyVisited = new LinkedHashSet<Vertex>();
		LinkedHashSet<Vertex> toVisit = new LinkedHashSet<Vertex>();
		Vertex tmp;
		toVisit.add(iVertex);
		while (!toVisit.isEmpty()) {
			iterator2 = toVisit.iterator();
			Vertex current = iterator2.next();
			toVisit.remove(current);
			alreadyVisited.add(current);
			if (equalHeightAndCapacity(current, iVertex) && !current.stable) {
				plateau.add(current);
				iterator = current.neighbours.iterator();
				while (iterator.hasNext()) {
					tmp = iterator.next();
					if (!alreadyVisited.contains(tmp)) {
						toVisit.add(tmp);
					}
				}
			}
		}
		return plateau;
	}

	// Finds the border (or wall) of the plateau passed in.
	static LinkedHashSet<Vertex> getWall(LinkedHashSet<Vertex> iPlateau) {
		LinkedHashSet<Vertex> wall = new LinkedHashSet<Vertex>();
		Iterator<Vertex> plateauIterator, neighboursIterator;
		plateauIterator = iPlateau.iterator();
		Vertex tmp1, tmp2;
		while (plateauIterator.hasNext()) {
			tmp1 = plateauIterator.next();
			neighboursIterator = tmp1.neighbours.iterator();
			while (neighboursIterator.hasNext()) {
				tmp2 = neighboursIterator.next();
				if (!wall.contains(tmp2)) {
					if (new HeightAndCapacityComparator().compare(tmp1, tmp2) == -1 || tmp2.stable) {
						wall.add(tmp2);
					}
				}
			}
		}
		return wall;
	}

	// Finds the lowest (considering height and capacity) vertex in a set
	static Vertex getShortestWall(LinkedHashSet<Vertex> iWall) {
		Vertex shortestWall = null, current = null;
		Iterator<Vertex> wallIterator = iWall.iterator();
		while (wallIterator.hasNext()) {
			current = wallIterator.next();
			if ( shortestWall == null )
				shortestWall = current;
			else if (new HeightAndCapacityComparator().compare(current, shortestWall) == -1) {
				shortestWall = current;
			}
		}
		return shortestWall;
	}

	// Uses shortest wall to determine id we need to update the capacities of input plateau.
	// If shortest wall is stable, marks whole plateau as stable
	static void updateCapacities(LinkedHashSet<Vertex> iPlateau, Vertex shortestWall) {
		Iterator<Vertex> plateauIterator = iPlateau.iterator();
		Vertex current = plateauIterator.next();
		int plateauHeightAndCapacity = current.capacity + current.height;
		int wallHeightAndCapacity = shortestWall.capacity + shortestWall.height;
		int capacityIncrement = wallHeightAndCapacity > plateauHeightAndCapacity ? wallHeightAndCapacity - plateauHeightAndCapacity : 0;
		plateauIterator = iPlateau.iterator();
		while (plateauIterator.hasNext()) {
			current = plateauIterator.next();
			if (capacityIncrement>0) {
				current.capacity += capacityIncrement;
			}
			// If the shortest wall is stable, I can mark all plateau as stable
			// (there is no way its capacity can further increase).
			current.stable = shortestWall.stable;
		}
	}

	// Checks if vertexes have same height + capacity.
	private static boolean equalHeightAndCapacity (Vertex v1, Vertex v2) {
		return v1.height + v1.capacity == v2.height + v2.capacity;
	}
	
}
